

/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM36 判断是不是平衡二叉树
 * <a href="https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=295&tqId=23250&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2022-12-29
 * Time: 19:59
 */

//思路：对于父节点，需要确定两个子节点深度之差小于一。对于作为子节点的立场，需要向自己的上一级节点传递的自己深度
//     因此如果从根节点向下便利，每次我们均需要求出左右子树的深度来比较，时间复杂度为O(n*n)，而我们利用回溯，即让
//     子节点向上传递自己的深度既可以做到时间复杂度为O（n).
class TreeNode {
    TreeNode left;
    TreeNode right;
    int val;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        //空树为平衡二叉树
        if (root == null) {
            return true;
        }
        return deep(root) != -1;
    }

    /**
     * 当左右子树的深度差大于1的时候，返回-1
     * 否则返回以当前结点为根节点的子树的深度
     */
    private int deep(TreeNode treeNode) {
        //判空处理
        if (treeNode == null) {
            return 0;
        }
        //处理左子树
        int left = deep(treeNode.left);
        if (left == -1) {
            return -1;
        }
        //处理右子树
        int right = deep(treeNode.right);
        if (right == -1) {
            return -1;
        }
        //判断左右子树深度差是否大于1
        if((left - right) > 1 || (right - left) > 1) {
            return -1;
        }
        //向上一级结点传递自己的深度
        return Math.max(left,right) + 1;
    }
}
